package org.example.algorithm.dp;

//494. 目标和
public class FindTargetSumWaysSolution {
    private int count = 0;

    public static void main(String[] args) {
        int[] nums = {1};
        int target = 1;
        FindTargetSumWaysSolution solution = new FindTargetSumWaysSolution();
        int res = solution.findTargetSumWays(nums, target);
        System.out.println(res);
    }
    //回溯
    public int findTargetSumWays(int[] nums, int target) {
        doFindTarget(nums, target, 0);
        return count;
    }

    private void doFindTarget(int[] nums, int target, int index) {
        if (index == nums.length-1) {
            if (target == nums[index] || target == -nums[index]) {
                count++;
                if (nums[index] == 0) {
                    count++;
                }
            }
            return;
        }
        doFindTarget(nums, target-nums[index], index+1);
        doFindTarget(nums, target+nums[index], index+1);
    }

    //节省内存版
    public int findTargetSumWays1(int[] nums, int target) {
        if (nums.length == 0) {
            return 0;
        }
        int sum = 0;
        for (int i=0;i<nums.length;i++) {
            sum += nums[i];
        }
        if (sum < target || (sum - target) % 2 != 0) {
            return 0;
        }
        int negative = (sum - target) / 2;
        int[] dp = new int[negative+1];
        if (nums[0] <= negative) {
            dp[nums[0]] = 1;
        }
        //注意！！！，nums[0]=0时，选择或者不选择和都为0，所以dp[0][0]=2
        if (nums[0] == 0) {
            dp[0] = 2;
        } else {
            dp[0] = 1;
        }
        for (int i=1;i<nums.length;i++) {
            for (int j=negative;j>=0;j--) {
                if (nums[i] <= j) {
                    dp[j] = dp[j] + dp[j-nums[i]];
                }
            }
        }
        return dp[negative];
    }

    //输入：nums = [1,1,1,1,1], target = 3
    //dp[i][j]代表【0，i】和为j的数目
    //假设前边使用“-”的元素和为negative，则使用“+”的元素和为sum-negative
    //sum - 2 * negative = target
    //negative = (sum - target) / 2
    public int findTargetSumWays2(int[] nums, int target) {
        if (nums.length == 0) {
            return 0;
        }
        int sum = 0;
        for (int i=0;i<nums.length;i++) {
            sum += nums[i];
        }
        if (sum < target || (sum - target) % 2 != 0) {
            return 0;
        }
        int negative = (sum - target) / 2;
        int[][] dp = new int[nums.length][negative+1];
        if (nums[0] <= negative) {
            dp[0][nums[0]] = 1;
        }
        //注意！！！，nums[0]=0时，选择或者不选择和都为0，所以dp[0][0]=2
        if (nums[0] == 0) {
            dp[0][0] = 2;
        } else {
            dp[0][0] = 1;
        }
        for (int i=1;i<nums.length;i++) {
            for (int j=0;j<=negative;j++) {
                if (nums[i] > j) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]];
                }
            }
        }
        return dp[nums.length-1][negative];
    }
}
